package version1;

/**
 * @author zhangjiayuan@qipeipu.com
 * @date 2019/1/6 12:55
 * @since 1.0.0
 */
public class Kmp2 {
    public static int[] Next(String ps) {
        char[] psChar = ps.toCharArray();
        int[] next = new int[psChar.length];
        int k = -1;
        next[0] = k;
        int j = 0;
        while (j < psChar.length -1) {
            if (k == -1 || psChar[j] == psChar[k]) {
                j++;
                k++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
    public static int kmp(String ts,String ps){
        char[] tsChars = ts.toCharArray();
        char[] psChars = ps.toCharArray();
        int i = 0;
        int j = 0;
        int[] next = Kmp2.Next(ps);
        while(i<tsChars.length && j<psChars.length){
            if(j == -1 || tsChars[i] == psChars[j]){
                i++;
                j++;
            }else{
                j = next[j];   //  i不变，j直接回溯到next[ j ]值
            }
        }
        if(j == psChars.length){
            return i-j;
        }else{
            return -1;
        }
    }

    public static void main(String[] args) {
        long begin = System.nanoTime();
        int result = Kmp2.kmp("btbtbtbtbtr",
                "btbtr");
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println(end-begin);
    }
}
